/**
 * Standard heapsort.
 */
template <typename Comparable>///模板化，便于替换数据类型
void heapsort( vector<Comparable> & a )///堆排序的实现
{
  for( int i = a.size( ) / 2 - 1; i >= 0; --i )  /* buildHeap */ ///建最大堆
      percDown( a, i, a.size( ) );///从堆中次后排元素开始降堆，使其形成有序的最大堆
    for( int j = a.size( ) - 1; j > 0; --j ) /* deleteMax */ ///依次将最大值弹到最后从而得到一个从小到大排列的数组
    {
      std::swap( a[ 0 ], a[ j ] );///将a[0]处的最大元素弹到堆的最后，并视其不再位于堆中  
      percDown( a, 0, j );///对现在的a[0]降堆，使除弹出元素外的元素重新排列
    }
}

/**
 * Internal method for heapsort.
 * i is the index of an item in the heap.
 * Returns the index of the left child.
 */
inline int leftChild( int i )///堆排序中leftChild函数的实现，获得堆中下标为i元素的左孩子元素的下标
{
  return 2 * i + 1;///根据堆的满二叉树特性，返回a[i]左孩子的下标
}

/**
 * Internal method for heapsort that is used in
 * deleteMax and buildHeap.
 * i is the position from which to percolate down.
 * n is the logical size of the binary heap.
 */
template <typename Comparable>///模板化，便于替换数据类型
void percDown( vector<Comparable> & a, int i, int n )///堆排序中percDown函数的实现，将a[i]在size为n的堆中降堆
{
    int child;///用于向下降堆的递归
    Comparable tmp;///用于暂存需要降堆的数据

    for( tmp = std::move( a[ i ] ); leftChild( i ) < n; i = child )///递归，从a[i]开始依次向下降堆使其满足最大堆的条件
    {
      child = leftChild( i );///从a[i]的左孩子开始判断
      if( child != n - 1 && a[ child ] < a[ child + 1 ] ）///判断哪个孩子更大
	  ++child;///移动到更大的孩子上进行操作
      if( tmp < a[ child ] )///判断a[i]是否比其最大的孩子小
	a[ i ] = std::move( a[ child ] );///若是则交换二者位置实现降堆
      else///若已完成降堆满足堆的条件则退出
	break;
    }
    a[ i ] = std::move( tmp );///将tmp中暂存的数据放到最终结束降堆的a[i]里
}

/**
 * Mergesort algorithm (driver).
 */
template <typename Comparable>///模板化，便于替换数据类型
void mergeSort( vector<Comparable> & a )///合并排序的接口
{
  vector<Comparable> tmpArray( a.size( ) );///建一个和a相同大小的空数组用于存放排序后的有序数组
  mergeSort( a, tmpArray, 0, a.size( ) - 1 );///对数组a合并排序
}

/**
 * Internal method that makes recursive calls.
 * a is an array of Comparable items.
 * tmpArray is an array to place the merged result.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>///模板化，便于替换数据类型
void mergeSort( vector<Comparable> & a,
                vector<Comparable> & tmpArray, int left, int right )///合并排序的实现，通过递归调用完成排序
{
  if( left < right )///当数列中所含元素大于等于2时进行操作
  {
      int center = ( left + right ) / 2;///将数列一分为二分别排序
      mergeSort( a, tmpArray, left, center );///对左子列排序
      mergeSort( a, tmpArray, center + 1, right );///对右子列排序
      merge( a, tmpArray, left, center + 1, right );///将两有序子列合并后放回a
  }
}

/**
 * Internal method that merges two sorted halves of a subarray.
 * a is an array of Comparable items.
 * tmpArray is an array to place the merged result.
 * leftPos is the left-most index of the subarray.
 * rightPos is the index of the start of the second half.
 * rightEnd is the right-most index of the subarray.
 */
template <typename Comparable>///模板化，便于替换数据类型
void merge( vector<Comparable> & a, vector<Comparable> & tmpArray,
            int leftPos, int rightPos, int rightEnd )///合并排序中merge函数的实现，合并a中左右两个有序子列
{
  int leftEnd = rightPos - 1;///左子列的尾元素下标
  int tmpPos = leftPos;///用于暂存tmpArray中需存放元素的下标
  int numElements = rightEnd - leftPos + 1;///所需排序数列的总元素个数

  // Main loop
  while( leftPos <= leftEnd && rightPos <= rightEnd )///两子列均未完全排序时
      if( a[ leftPos ] <= a[ rightPos ] )///比较左子列的头元素与右子列的头元素
	tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );///若左子列头元素较小则将其存入tmpArray，并后移左子列头元素下标
      else
	tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );///若右子列头元素较小则将其存入tmpArray，并后移右子列头元素下标

  while( leftPos <= leftEnd )///右子列已完成排序而左子列未完成时
    tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );///将左子列剩余元素依次存入tmpArray

  while( rightPos <= rightEnd )///左子列已完成排序而右子列未完成时
    tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );///将右子列剩余元素依次存入tmpArray

  // Copy tmpArray back
  for( int i = 0; i < numElements; ++i, --rightEnd )///将完成排序的tmpArray复制回a
    a[ rightEnd ] = std::move( tmpArray[ rightEnd ] );///从右向左依次将tmpArray中暂存的元素放回数组a中，完成从小到大的排序
}

template <typename Comparable>///模板化，便于替换数据类型
void SORT( vector<Comparable> & items )///快速排序的一种实现，选定数据为数组中间元素
{
  if( items.size( ) > 1 )///当需要排序的数组元素个数大于1时进行排序操作
  {
      vector<Comparable> smaller;///用于存放比选定数据小的元素
      vector<Comparable> same;///用于存放与选定数据相等的元素
      vector<Comparable> larger;///用于存放比选定数据大的元素
        
      auto chosenItem = items[ items.size( ) / 2 ];///选择数组中间的元素作为选定数据
        
      for( auto & i : items )///对数组中元素从头开始与选定数据比较并分为三类
      {
	  if( i < chosenItem )///若该元素小于选定数据
	    smaller.push_back( std::move( i ) );///将其放入smaller数组中
	  else if( chosenItem < i )///若该元素大于选定数据
	    larger.push_back( std::move( i ) );///将其放入larger数组中
	  else///若该元素等于选定数据
	    same.push_back( std::move( i ) );///将其放入same数组中
      }
        
      SORT( smaller );///递归调用，对smaller再排序
      SORT( larger );///递归调用，对larger再排序
        
      std::move( begin( smaller ), end( smaller ), begin( items ) );///将smaller中的元素依次放回items
      std::move( begin( same ), end( same ), begin( items ) + smaller.size( ) );///将same中的元素接着放回items
      std::move( begin( larger ), end( larger ), end( items ) - larger.size( ) );///将larger中的元素接着依次放回items
  }
}

/**
 * Quicksort algorithm (driver).
 */
template <typename Comparable>///模板化，便于替换数据类型
void quicksort( vector<Comparable> & a )///快速排序的接口
{
  quicksort( a, 0, a.size( ) - 1 );///对数组a从头到尾排序
}

/**
 * Return median of left, center, and right.
 * Order these and hide the pivot.
 */
template <typename Comparable>///模板化，便于替换数据类型
const Comparable & median3( vector<Comparable> & a, int left, int right )///快速排序中一种选择选定数据的方法——三平均分区法，使选定数据不太大也不太小提高效率
{
  int center = ( left + right ) / 2;///取数组中间元素

  //调整头元素、中间元素和尾元素的位置使其顺序排列
  if( a[ center ] < a[ left ] )///比较头元素和中间元素
    std::swap( a[ left ], a[ center ] );///调整位置，顺序排列
  if( a[ right ] < a[ left ] )///比较头元素和尾元素
    std::swap( a[ left ], a[ right ] );///调整位置，顺序排列
  if( a[ right ] < a[ center ] )///比较中间元素和尾元素
    std::swap( a[ center ], a[ right ] );///调整位置，顺序排列

  std::swap( a[ center ], a[ right - 1 ] );///将三者中大小为中间的元素作为选定数据放在次后位置
  return a[ right - 1 ];///返回该选定数据
}

/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * a is an array of Comparable items.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>///模板化，便于替换数据类型
void quicksort( vector<Comparable> & a, int left, int right )///快速排序的另一种实现，通过递归调用完成排序
{
  if( left + 10 <= right )///对长度大于等于10的数列进行快速排序
  {
      const Comparable & pivot = median3( a, left, right );///用midian3方法取头元素、中间元素、尾元素的中间值为选定数据

      //分区
      int i = left, j = right - 1;///从两端开始分区
      for( ; ; )
      {
	  while( a[ ++i ] < pivot ) { }///从左向右找到大于等于选定数据的元素
	  while( pivot < a[ --j ] ) { }///从右向左找到小于等于选定数据的元素
	  if( i < j )///当两元素不重合，即两元素之间仍有元素时
	    std::swap( a[ i ], a[ j ] );///交换两元素位置，使左元素小于选定数据而右元素大于选定数据
	  else///当两元素重合时
	    break;///完成分区退出循环
      }

      std::swap( a[ i ], a[ right - 1 ] );///将选定数据放在两分区之间

      quicksort( a, left, i - 1 );///递归，对小于等于选定数据的左子列排序
      quicksort( a, i + 1, right );///递归，对大于等于选定数据的右子列排序
  }
  else///对长度小于10的数列进行插入排序
      insertionSort( a, left, right );
}
